package linear.chain;

public class MyLinkedList {

    public Node head;

    //创建链表
    public void create() {
        //创建节点
        Node a = new Node('A');
        Node b = new Node('B');
        Node c = new Node('C');
        Node d = new Node('D');
        Node e = new Node('E');
        Node f = new Node('F');

        //head是类的属性 属性的操作应当在方法中进行
        this.head = a;
        //以上是单独的节点 现在让他们串起来
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;
    }

    //打印链表
    public void display() {
        Node cur = head;
        if (cur == null) {
            System.out.println("链表为空");
            return;
        }
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //头插法
    public void addFirst(char key) {
        //新建一个节点
        Node node = new Node(key);
        //头节点 指向新的node节点 node节点 指向头节点之前指向的节点
        node.next = head;
        this.head = node;
    }

    //尾插法
    public void addLast(char key) {
        //尾插法 要找到最后一个节点
        Node node = new Node(key);
        //头节点不能动 不然遍历之后就找不到了
        //如果当前链表是空的 head 就是空 出现空指针异常
        Node cur = head;
        if (cur == null) {
            addFirst(key);
        } else {
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //查找是否包含关键字a
    public boolean contains(char key) {
        //便利去查找
        Node cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到链表长度
    public int size() {
        int size = 0;
        Node cur = this.head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }

        return size;
    }

    //任意位置插入
    public void indexAdd(int index, char key) {
        //1.判断 index位置是否合法
        if (index < 0 || index > size()) {
            System.out.println("index 位置不合法");
            return;
        }
        //2.判断当前链表是否为空 空就直接头插法
        Node node = new Node(key);
        Node cur = this.head;
        if (cur == null) {
            addFirst(key);
            return;
        }

        //3.如果是最后一个节点 直接尾插法
        if (index == size()) {
            addLast(key);
            return;
        }

        //4.如果不是空 遍历到指定节点 是要找到前面一个位置操作 插入
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;

    }

    //删除第一次出现的关键字A
    public boolean removeKey(char key) {
        //1.可能存在链表为空的情况
        if (this.head == null) {
            System.out.println("链表为空 不能删除");
            return false;
        }
        //头节点 如果是要删除的节点 才需要单独处理
        if (this.head.val == key) {
            this.head = this.head.next;
            return true;
        }
        //删除那个节点 要找到删除节点的前驱节点
        Node cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //可以对上面的操作 进行循环   但是也可以通过一次遍历实现
    //删除所有值为key的节点
    public Node removeAllKey(int key) {
        if (this.head == null) {
            return null;
        }
        Node prev = this.head;
        Node cur = this.head.next;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (this.head.val == key) {
            this.head = this.head.next;
        }
        return this.head;
    }


    //清空链表
    public void clear() {
        //1.简单粗暴的方法：将头节点置为空head = null；即可
        //2.细腻温柔的做法：将每一个节点都置为空
        this.head = null;
    }

}
